package Leetcode第二期;

/**
 * @author : K k
 * @date : 15:17 2020/9/16
 * 给定一个非空二叉树，返回其最大路径和。
 *
 * 本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[1,2,3]
 *
 *        1
 *       / \
 *      2   3
 *
 * 输出：6
 * 示例 2：
 *
 * 输入：[-10,9,20,null,null,15,7]
 *
 *    -10
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 输出：42
 */
public class 二叉树中的最大路径和_124 {
    int max_size=Integer.MIN_VALUE;

    //BFS
    public int maxPathSum(TreeNode root) {
        bfsSolver(root);
        return max_size;
    }

    private int bfsSolver(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //计算左右的最大路径  减去负数路径
        int left=Math.max(bfsSolver(root.left),0);
        int right=Math.max(bfsSolver(root.right),0);
        //更新最大值 记录任何一条路径更新最大值
        max_size=Math.max(max_size,root.val+left+right);

        //返回一条左右路径中比较大的一条
        return root.val+Math.max(left,right);
    }

    public static void main(String[] args) {
        /*二叉树中的最大路径和_124 x=new 二叉树中的最大路径和_124();
        System.out.println(x.bfsSolver(new TreeNode(0)));*/
        int x=12321;

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        System.out.println(revertedNumber+"  "+x);

    }

}
